package LC;

import java.util.*;

/**
 * https://leetcode.com/problems/group-anagrams/description/
 * Given an array of strings, group anagrams together.
 * For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
 * Return:
 * [
 * ["ate", "eat","tea"],
 * ["nat","tan"],
 * ["bat"]
 * ]
 * Note: All inputs will be in lower-case.
 */
public class LC_049_GroupAnagrams_Sort_HashMap {
    public static void main(String[] args) {
        String[] s = {"eat", "tea", "tan", "ate", "nat", "bat"};
        List<List<String>> res = Solution.groupAnagrams(s);
        System.out.println(res);
    }

    static class Solution {
        static List<List<String>> groupAnagrams(String[] strs) {
            HashMap<String, List<String>> map = new HashMap<>();

            for (String s : strs) {
                char[] str2char = s.toCharArray();
                Arrays.sort(str2char);
                String sortedStr = String.valueOf(str2char);

                if (map.containsKey(sortedStr))
                    map.get(sortedStr).add(s);
                else {
                    ArrayList<String> tmp = new ArrayList<>();
                    tmp.add(s);
                    map.put(sortedStr, tmp);
                }
            }

            List<List<String>> result = new ArrayList<>();
            for (List<String> list : map.values()) {
                Collections.sort(list);
                result.add(list);
            }

            return result;
        }
    }
}
